package Leetcode;

import base.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * 一个节点也可以是它自己的祖先
 */
public class 力扣236_二叉树的最近公共祖先 {

    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        TreeNode g = new TreeNode(7);

        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;

        TreeNode treeNode = lowestCommonAncestor2(a, b, c);
        System.out.println(treeNode.val);
    }

    /**
     * 存储每个节点对应的父节点 然后从p/q网上寻找父节点走一遍路径 判断是否重复 来找到最近节点
     */
    static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<Integer, TreeNode> parent = new HashMap<>();
        Set<Integer> path = new HashSet<>();
        parentDfs(root, parent);
        while (p != null) {
            path.add(p.val);
            p = parent.get(p.val);
        }
        while (q != null) {
            boolean add = path.add(q.val);
            if (!add) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }

    /**
     * 递归节点 将节点值和节点的父节点进行映射
     */
    static void parentDfs(TreeNode root, Map<Integer, TreeNode> parent) {
        if (root != null) {
            if (root.left != null) {
                parent.put(root.left.val, root);
                parentDfs(root.left, parent);
            }
            if (root.right != null) {
                parent.put(root.right.val, root);
                parentDfs(root.right, parent);
            }
        }
    }

    /**
     * 方式2 使用递归的方式  每次dfs 寻找左右节点是否有p/q或者本节点是p/q
     */
    static TreeNode result = null;

    static TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        boolean parentDfs = findParentDfs(root, p, q);
        return result;
    }


    static boolean findParentDfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        boolean parentLeft = findParentDfs(root.left, p, q);
        boolean parentRight = findParentDfs(root.right, p, q);
        if ((parentLeft && parentRight) || ((root.val == p.val || root.val == q.val) && (parentLeft || parentRight))) {
            result = root;
        }
        return (parentLeft || parentRight) || (root.val == p.val || root.val == q.val);
    }


}
